{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Count Univalue Subtrees"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #tree #depth-first-search #binary-tree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #树 #深度优先搜索 #二叉树"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: countUnivalSubtrees"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #统计同值子树"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定一个二叉树，统计该二叉树数值相同的子树个数。</p>\n",
    "\n",
    "<p>同值子树是指该子树的所有节点都拥有相同的数值。</p>\n",
    "\n",
    "<p><strong>示例：</strong></p>\n",
    "\n",
    "<pre><strong>输入: </strong>root = [5,1,5,5,5,null,5]\n",
    "\n",
    "              5\n",
    "             / \\\n",
    "            1   5\n",
    "           / \\   \\\n",
    "          5   5   5\n",
    "\n",
    "<strong>输出:</strong> 4\n",
    "</pre>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [count-univalue-subtrees](https://leetcode.cn/problems/count-univalue-subtrees/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [count-univalue-subtrees](https://leetcode.cn/problems/count-univalue-subtrees/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[5,1,5,5,5,null,5]', '[]', '[5,5,5,5,5,null,5]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "        \n",
    "    def countUnivalSubtrees(self, root: TreeNode) -> int:\n",
    "        if not root:\n",
    "            return 0\n",
    "        \n",
    "        self.count = 0\n",
    "        self.is_uni(root)\n",
    "        return self.count\n",
    "    \n",
    "    def is_uni(self, node: TreeNode) -> bool:\n",
    "        if not node.left and not node.right:\n",
    "            self.count += 1\n",
    "            return True\n",
    "        is_uni = True\n",
    "        if node.left:\n",
    "            is_uni = self.is_uni(node.left) and is_uni and (node.left.val == node.val)\n",
    "        if node.right:\n",
    "            is_uni = self.is_uni(node.right) and is_uni and (node.right.val == node.val)\n",
    "        self.count += is_uni\n",
    "        return is_uni\n",
    "        \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def countUnivalSubtrees(self, root: Optional[TreeNode]) -> int:\n",
    "        result = 0\n",
    "        def dfs(node):\n",
    "            if node:\n",
    "                left, right = dfs(node.left), dfs(node.right)\n",
    "                flag = left is None or left == node.val\n",
    "                flag &= right is None or right == node.val\n",
    "                if flag:\n",
    "                    nonlocal result\n",
    "                    result += 1\n",
    "                    return node.val\n",
    "                return float('inf')\n",
    "        dfs(root)\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def countUnivalSubtrees(self, root: Optional[TreeNode]) -> int:\n",
    "        if not root: return 0\n",
    "        self.cnt = 0\n",
    "        \n",
    "        self.help(root,-1)\n",
    "        return self.cnt\n",
    "    \n",
    "    def help(self,root, parent):  \n",
    "        if not root:\n",
    "            return True\n",
    "        \n",
    "        left = self.help(root.left, root.val)\n",
    "        right = self.help(root.right, root.val)\n",
    "\n",
    "        if left and right:\n",
    "            self.cnt += 1\n",
    "            return root.val == parent\n",
    "        return False\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Info:\n",
    "    def __init__(self, subTree=True, val = None):\n",
    "        self.subTree = subTree\n",
    "        self.val = val\n",
    "class Solution:\n",
    "    def countUnivalSubtrees(self, root: Optional[TreeNode]) -> int:\n",
    "        ans = 0\n",
    "        def dfs(root):\n",
    "            nonlocal ans\n",
    "            if not root:\n",
    "                return Info()\n",
    "            left = dfs(root.left)\n",
    "            right = dfs(root.right)\n",
    "            if left.subTree and right.subTree:\n",
    "                if left.val == None and right.val==None:\n",
    "                    ans += 1\n",
    "                    return Info(True, root.val)\n",
    "                if not left.val and right.val == root.val:\n",
    "                    ans += 1\n",
    "                    return Info(True, root.val)\n",
    "                if not right.val and left.val == root.val:\n",
    "                    ans += 1\n",
    "                    return Info(True, root.val)\n",
    "                if root.val == left.val == right.val:\n",
    "                    ans += 1\n",
    "                    return Info(True, root.val)\n",
    "            return Info(False, None)\n",
    "        dfs(root)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def countUnivalSubtrees(self, root: Optional[TreeNode]) -> int:\n",
    "        # helper用于判断以当前节点为根的子树是否是同值子树\n",
    "        def helper(node):\n",
    "            nonlocal count  # 使用nonlocal声明外部变量count\n",
    "            if not node:\n",
    "                return True\n",
    "            left_uni = helper(node.left)   # 左子树是否是同值子树 \n",
    "            right_uni = helper(node.right) # 右子树是否是同值子树\n",
    "            # 如果左右子树都是同值子树\n",
    "            if left_uni and right_uni:\n",
    "                # 当前节点的值与左右子节点的值相等，或者当前节点没有左右子节点(叶子节点)\n",
    "                if (node.left and node.left.val == node.val) or not node.left:\n",
    "                    if (node.right and node.right.val == node.val) or not node.right:\n",
    "                        count += 1   # 统计同值子树的数量\n",
    "                        return True  # 返回True，表示当前节点为根的子树也是同值子树\n",
    "            return False  # 如果不满足同值子树的条件，返回False\n",
    "\n",
    "        count = 0\n",
    "        helper(root)\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def countUnivalSubtrees(self, root: Optional[TreeNode]) -> int:\n",
    "        cnt = 0\n",
    "        def dfs(node):\n",
    "            nonlocal cnt\n",
    "            if node == None:\n",
    "                return None\n",
    "            if node.left == None and node.right == None:\n",
    "                cnt += 1\n",
    "                return node.val\n",
    "            left = dfs(node.left)\n",
    "            right = dfs(node.right)\n",
    "            if left == right == node.val or (left == None and right == node.val) or (right == None and left == node.val):\n",
    "                cnt += 1\n",
    "                return node.val\n",
    "            return inf\n",
    "        dfs(root)\n",
    "        return cnt\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def countUnivalSubtrees(self, root: Optional[TreeNode]) -> int:\n",
    "        ans = 0\n",
    "        def dfs(node):\n",
    "            nonlocal ans \n",
    "            if not node:\n",
    "                return [True, 'any']\n",
    "            l, r = dfs(node.left), dfs(node.right)\n",
    "            if l[0] and r[0] and (l[1] == 'any' or l[1] == node.val) and (r[1] == 'any' or r[1] == node.val):\n",
    "                ans += 1\n",
    "                return [True, node.val]\n",
    "            return [False, 'no']\n",
    "        \n",
    "        dfs(root)\n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    num = 0\n",
    "\n",
    "    def dfs(self, root):\n",
    "        if root is None:\n",
    "            return \n",
    "        if root.left is None and root.right is None:\n",
    "            self.num += 1\n",
    "            return root.val, True\n",
    "        unival = True\n",
    "        if root.left is not None:\n",
    "            left_val, left_unival = self.dfs(root.left)\n",
    "            if left_val != root.val or not left_unival:\n",
    "                unival = False\n",
    "        if root.right is not None:\n",
    "            right_val, right_unival = self.dfs(root.right)\n",
    "            if right_val != root.val or not right_unival:\n",
    "                unival = False\n",
    "        if unival:\n",
    "            self.num += 1\n",
    "        return root.val, unival\n",
    "\n",
    "    def countUnivalSubtrees(self, root: Optional[TreeNode]) -> int:\n",
    "        self.dfs(root)\n",
    "        return self.num\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def countUnivalSubtrees(self, root: Optional[TreeNode]) -> int:\n",
    "        self.cnt = 0\n",
    "        self.isSame(root)\n",
    "        return self.cnt\n",
    "\n",
    "    def isSame(self, node):\n",
    "        if node is None:\n",
    "            return True\n",
    "        ans = True\n",
    "        leftAns = self.isSame(node.left)\n",
    "        rightAns = self.isSame(node.right)\n",
    "        if node.left is not None:\n",
    "            if node.val != node.left.val or not leftAns:\n",
    "                ans = False\n",
    "        if node.right is not None:\n",
    "            if node.val != node.right.val or not rightAns:\n",
    "                ans = False\n",
    "        if ans:\n",
    "            self.cnt += 1\n",
    "        return ans\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def countUnivalSubtrees(self, root: TreeNode) -> int:\n",
    "        self.ans = 0\n",
    "        def dfs(node):\n",
    "            if not node:\n",
    "                return None\n",
    "            if not node.left and not node.right:\n",
    "                self.ans += 1\n",
    "                return node.val\n",
    "            left = dfs(node.left)\n",
    "            right = dfs(node.right)\n",
    "            if left == right == node.val or (left is None and right == node.val) or (right is None and left == node.val):\n",
    "                self.ans += 1\n",
    "                return node.val\n",
    "            return inf\n",
    "        \n",
    "        dfs(root)\n",
    "        return self.ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def countUnivalSubtrees(self, root: Optional[TreeNode]) -> int:\n",
    "        count = 0\n",
    "        if not root:\n",
    "            return 0\n",
    "        def dfs(root):\n",
    "            if not root.left and not root.right:\n",
    "                nonlocal count\n",
    "                count += 1\n",
    "                return True\n",
    "            \n",
    "            isuni = True\n",
    "\n",
    "            if root.left:\n",
    "                isuni = dfs(root.left) and isuni and root.left.val == root.val\n",
    "            \n",
    "            if root.right:\n",
    "                isuni = dfs(root.right) and isuni and root.right.val == root.val\n",
    "\n",
    "            count += isuni\n",
    "            return isuni\n",
    "        dfs(root)\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countUnivalSubtrees(self, root):\n",
    "        if root is None: return 0\n",
    "        self.count = 0\n",
    "        self.is_uni(root)\n",
    "        return self.count\n",
    "\n",
    "    def is_uni(self, node):\n",
    "\n",
    "        # base case - if the node has no children this is a univalue subtree\n",
    "        if node.left is None and node.right is None:\n",
    "\n",
    "            # found a univalue subtree - increment\n",
    "            self.count += 1\n",
    "            return True\n",
    "\n",
    "        is_uni = True\n",
    "\n",
    "        # check if all of the node's children are univalue subtrees and if they have the same value\n",
    "        # also recursively call is_uni for children\n",
    "        if node.left is not None:\n",
    "            is_uni = self.is_uni(node.left) and is_uni and node.left.val == node.val\n",
    "\n",
    "        if node.right is not None:\n",
    "            is_uni = self.is_uni(node.right) and is_uni and node.right.val == node.val\n",
    "\n",
    "        # increment self.res and return whether a univalue tree exists here\n",
    "        self.count += is_uni\n",
    "        return is_uni\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def countUnivalSubtrees(self, root: Optional[TreeNode]) -> int:\n",
    "        self.count = 0\n",
    "        self.is_vaild_part(root, 0)\n",
    "        return self.count\n",
    "    \n",
    "    def is_vaild_part(self, node, val):\n",
    "        if node is None:\n",
    "            return True\n",
    "        \n",
    "        if not all([self.is_vaild_part(node.left, node.val), self.is_vaild_part(node.right, node.val)]):\n",
    "            return False\n",
    "        self.count += 1\n",
    "        return node.val == val    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def countUnivalSubtrees(self, root: Optional[TreeNode]) -> int:\n",
    "        ret=0\n",
    "        def f(root):\n",
    "            nonlocal ret\n",
    "            if root==None:\n",
    "                return None\n",
    "            leftval=f(root.left)\n",
    "            rightval=f(root.right)\n",
    "            if leftval==None:\n",
    "                leftval=root.val\n",
    "            if rightval==None:\n",
    "                rightval=root.val\n",
    "            if leftval==rightval==root.val and leftval!='a':\n",
    "                ret+=1\n",
    "                return root.val\n",
    "            else:\n",
    "                return 'a'\n",
    "        f(root)\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def countUnivalSubtrees(self, root: Optional[TreeNode]) -> int:\n",
    "        cnt = 0\n",
    "\n",
    "        def cnt_unival(node):\n",
    "            nonlocal cnt\n",
    "            if node is None:\n",
    "                return True, None\n",
    "            left_flag, left_val = cnt_unival(node.left)\n",
    "            right_flag, right_val = cnt_unival(node.right)\n",
    "            if left_flag and right_flag and (True if left_val is None or left_val == node.val else False) and (True if right_val is None or right_val == node.val else False):\n",
    "                cnt += 1\n",
    "                return True, node.val\n",
    "            else:\n",
    "                return False, None\n",
    "        \n",
    "        cnt_unival(root)\n",
    "        return cnt\n",
    "        \n",
    "\n",
    "            \n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def countUnivalSubtrees(self, root: Optional[TreeNode]) -> int:\n",
    "        if root is None: return 0\n",
    "        self.count = 0\n",
    "        self.is_uni(root)\n",
    "        return self.count\n",
    "\n",
    "    def is_uni(self, node):\n",
    "\n",
    "        # base case - if the node has no children this is a univalue subtree\n",
    "        if node.left is None and node.right is None:\n",
    "\n",
    "            # found a univalue subtree - increment\n",
    "            self.count += 1\n",
    "            return True\n",
    "\n",
    "        is_uni = True\n",
    "\n",
    "        # check if all of the node's children are univalue subtrees and if they have the same value\n",
    "        # also recursively call is_uni for children\n",
    "        if node.left is not None:\n",
    "            is_uni = self.is_uni(node.left) and is_uni and node.left.val == node.val\n",
    "\n",
    "        if node.right is not None:\n",
    "            is_uni = self.is_uni(node.right) and is_uni and node.right.val == node.val\n",
    "\n",
    "        # increment self.res and return whether a univalue tree exists here\n",
    "        self.count += is_uni\n",
    "        return is_uni\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "from collections import defaultdict\n",
    "class Solution:\n",
    "    def countUnivalSubtrees(self, root: Optional[TreeNode]) -> int:\n",
    "        \n",
    "        def helper(node):\n",
    "            nonlocal count\n",
    "            if not node:\n",
    "                return 0\n",
    "            if not node.left and not node.right:\n",
    "                count+=1\n",
    "                return 1\n",
    "            left = helper(node.left)\n",
    "            right= helper(node.right)\n",
    "            if not node.right and node.left and left and node.val==node.left.val:\n",
    "                count+=1\n",
    "                return 1\n",
    "            if not node.left and node.right and right and node.val==node.right.val:\n",
    "                count+=1\n",
    "                return 1\n",
    "            if node.left and node.right and left and right and node.val==node.left.val and node.val==node.right.val:\n",
    "                count+=1\n",
    "                return 1\n",
    "            return 0\n",
    "        count = 0\n",
    "        helper(root)\n",
    "        return count\n",
    "\n",
    "            \n",
    "                \n",
    "            \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def countUnivalSubtrees(self, root: Optional[TreeNode]) -> int:\n",
    "        \n",
    "        def find(node):\n",
    "            nonlocal count\n",
    "            if not node: return \n",
    "            l, r = find(node.left), find(node.right)\n",
    "            if not l and not r:\n",
    "                count += 1\n",
    "                return node   \n",
    "            if not l and r and r.val == node.val:\n",
    "                count += 1\n",
    "                return node\n",
    "            if not r and l and l.val == node.val:\n",
    "                count += 1\n",
    "                return node\n",
    "            if node and l and r:\n",
    "                if l.val ==r.val == node.val:\n",
    "                    count += 1\n",
    "                    return node  \n",
    "            return TreeNode(inf)\n",
    "        count = 0\n",
    "        find(root)\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def countUnivalSubtrees(self, root: Optional[TreeNode]) -> int:\n",
    "        def dfs(root):\n",
    "            if not root:\n",
    "                return []\n",
    "            return [root.val] + dfs(root.left) + dfs(root.right)\n",
    "        self.sum = 0\n",
    "        def check(root):\n",
    "            if not root:\n",
    "                return\n",
    "            if len(set(dfs(root))) == 1:\n",
    "                self.sum += 1\n",
    "            check(root.left)\n",
    "            check(root.right)\n",
    "        check(root)\n",
    "        return self.sum"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def countUnivalSubtrees(self, root: Optional[TreeNode]) -> int:\n",
    "        def dfs(node):\n",
    "            if not node:\n",
    "                return True\n",
    "            l = dfs(node.left)\n",
    "            r = dfs(node.right)\n",
    "            if (l and r) and (not node.left or node.left.val == node.val) and (not node.right or node.right.val == node.val):\n",
    "                self.count += 1\n",
    "                return True\n",
    "            else:\n",
    "                return False\n",
    "        self.count = 0\n",
    "        dfs(root)\n",
    "        return self.count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def countUnivalSubtrees(self, root: Optional[TreeNode]) -> int:\n",
    "        if not root: return 0\n",
    "        ans = 0\n",
    "        def dfs(root):\n",
    "            nonlocal ans\n",
    "            if not root.left and not root.right:\n",
    "                ans += 1\n",
    "                return True\n",
    "            \n",
    "            unique = True\n",
    "            if root.left:\n",
    "                unique = dfs(root.left) and unique and root.left.val == root.val\n",
    "            if root.right:\n",
    "                unique = dfs(root.right) and unique and root.right.val == root.val\n",
    "            ans += unique\n",
    "            return unique\n",
    "        dfs(root)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def countUnivalSubtrees(self, root: Optional[TreeNode]) -> int:\n",
    "        def is_uni(root: Optional[TreeNode]) -> bool:\n",
    "            nonlocal res\n",
    "            flg = True\n",
    "            if root.left:\n",
    "                flg = is_uni(root.left) and flg and root.val==root.left.val\n",
    "            if root.right:\n",
    "                flg = is_uni(root.right) and flg and root.val==root.right.val\n",
    "            if flg: res+=1\n",
    "            return flg\n",
    "        if not root: return 0\n",
    "        res = 0\n",
    "        is_uni(root)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def countUnivalSubtrees(self, root: Optional[TreeNode]) -> int:\n",
    "        cnt = 0\n",
    "        def dfs(root):\n",
    "            nonlocal cnt\n",
    "            if not root:\n",
    "                return \"Y\"\n",
    "\n",
    "            left, right = dfs(root.left), dfs(root.right)\n",
    "            if left in (\"Y\", root.val) and right in (\"Y\", root.val):\n",
    "                cnt += 1\n",
    "                return root.val\n",
    "            else:\n",
    "                return \"N\"\n",
    "        \n",
    "        dfs(root)\n",
    "        return cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def countUnivalSubtrees(self, root: Optional[TreeNode]) -> int:\n",
    "        #简单递归求解即可把\n",
    "        cnt,error=0,0\n",
    "        def dfs(x):\n",
    "            nonlocal cnt,error\n",
    "            if x is None:\n",
    "                return None\n",
    "            cnt+=1\n",
    "            l=dfs(x.left)\n",
    "            r=dfs(x.right)\n",
    "            if (l is None or l==x.val) and (r is None or r==x.val):\n",
    "                return x.val\n",
    "            error+=1\n",
    "            return 100\n",
    "        dfs(root)\n",
    "        print(cnt,error)\n",
    "        return cnt-error"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def dfsCheck(self, root: TreeNode):\n",
    "        if not root:\n",
    "            return None\n",
    "        if not root.left and not root.right:\n",
    "            self.ans += 1\n",
    "            return root.val\n",
    "        leftAns = self.dfsCheck(root.left)\n",
    "        rightAns = self.dfsCheck(root.right)\n",
    "        if leftAns == rightAns == root.val or (leftAns is None and rightAns == root.val) or (rightAns is None and leftAns == root.val):\n",
    "            self.ans += 1\n",
    "            return root.val\n",
    "        return inf\n",
    "\n",
    "    def countUnivalSubtrees(self, root: Optional[TreeNode]) -> int:\n",
    "        self.ans = 0\n",
    "        self.dfsCheck(root)\n",
    "        return self.ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def countUnivalSubtrees(self, root: Optional[TreeNode]) -> int:\n",
    "        if not root:\n",
    "            return 0\n",
    "        res = 0\n",
    "        def dfs(cur_node):\n",
    "            nonlocal res\n",
    "            if not cur_node.left and not cur_node.right:\n",
    "                res += 1\n",
    "                return True\n",
    "            is_uni = True\n",
    "            if cur_node.left:\n",
    "                is_uni = dfs(cur_node.left) and cur_node.val == cur_node.left.val and is_uni\n",
    "            if cur_node.right:\n",
    "                is_uni = dfs(cur_node.right) and cur_node.val == cur_node.right.val and is_uni\n",
    "            \n",
    "            res += is_uni\n",
    "            return is_uni\n",
    "        dfs(root)\n",
    "        return res\n",
    "            \n",
    "            \n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def countUnivalSubtrees(self, root: Optional[TreeNode]) -> int:\n",
    "        if root is None:\n",
    "            return 0\n",
    "        counter = 0\n",
    "\n",
    "        def helper(node):\n",
    "            nonlocal counter\n",
    "            leftbool = True\n",
    "            rightbool = True\n",
    "            if node.left:\n",
    "                leftbool = helper(node.left)\n",
    "            if node.right:\n",
    "                rightbool = helper(node.right)\n",
    "            if leftbool and rightbool:\n",
    "                if (node.left is None or node.val == node.left.val) and (node.right is None or node.val == node.right.val):\n",
    "                    counter += 1\n",
    "                    return True\n",
    "            return False\n",
    "        helper(root)\n",
    "        return counter"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def countUnivalSubtrees(self, root: Optional[TreeNode]) -> int:\n",
    "        \n",
    "        if not root: return 0\n",
    "        self.count = 0\n",
    "        def dfs(node, value):\n",
    "            if not node: return True\n",
    "            if not all([dfs(node.left, node.val), dfs(node.right, node.val)]):\n",
    "                return False\n",
    "            self.count += 1\n",
    "            return node.val == value\n",
    "    \n",
    "        dfs(root, root.val)\n",
    "        return self.count\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def countUnivalSubtrees(self, root: Optional[TreeNode]) -> int:\n",
    "        count = [0]\n",
    "        def dfs(n):\n",
    "            if not n: return True\n",
    "            if n.left == None and n.right == None:\n",
    "                count[0] +=1\n",
    "                return True\n",
    "\n",
    "            res = True\n",
    "\n",
    "            for c in (n.left, n.right):\n",
    "                if c and (dfs(c) is False or n.val != c.val):\n",
    "                    res = False\n",
    "            if res: count[0] +=1\n",
    "            return res\n",
    "        dfs(root)\n",
    "        return count[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "\n",
    "\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def __init__(self):\n",
    "        self._count = 0\n",
    "\n",
    "    def countUnivalSubtrees(self, root: Optional[TreeNode]) -> int:\n",
    "        return self.answer_1(root)\n",
    "\n",
    "    def answer_1(self, root):\n",
    "        self._dfs_1(root)\n",
    "        return self._count\n",
    "\n",
    "    def _dfs_1(self, node):\n",
    "        flag = True\n",
    "        if not node:\n",
    "            return flag\n",
    "\n",
    "        if node.left is None and node.right is None:\n",
    "            self._count += 1\n",
    "            return flag\n",
    "\n",
    "        if node.left:\n",
    "            flag =   self._dfs_1(node.left)   and node.left.val == node.val\n",
    "\n",
    "        if node.right:\n",
    "            flag =  self._dfs_1(node.right) and flag and  node.right.val == node.val\n",
    "\n",
    "        if flag:\n",
    "            self._count += 1\n",
    "        return flag"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def countUnivalSubtrees(self, root: Optional[TreeNode]) -> int:\n",
    "        if not root:\n",
    "            return 0\n",
    "        res = 0\n",
    "        def dfs(cur_node):\n",
    "            nonlocal res\n",
    "            if not cur_node.left and not cur_node.right:\n",
    "                res += 1\n",
    "                return True\n",
    "            is_uni = True\n",
    "            if cur_node.left:\n",
    "                is_uni = dfs(cur_node.left) and cur_node.val == cur_node.left.val and is_uni\n",
    "            if cur_node.right:\n",
    "                is_uni = dfs(cur_node.right) and cur_node.val == cur_node.right.val and is_uni\n",
    "            \n",
    "            res = res if not is_uni else res + 1\n",
    "            return is_uni\n",
    "        dfs(root)\n",
    "        return res\n",
    "            \n",
    "            \n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def countUnivalSubtrees(self, root: Optional[TreeNode]) -> int:\n",
    "        ans = 0 \n",
    "        if root is None:\n",
    "            return 0 \n",
    "        def dfs(root):\n",
    "            nonlocal ans \n",
    "            mx, mn = root.val, root.val\n",
    "            if root.left:\n",
    "                a, b = dfs(root.left)\n",
    "                mx = max(mx, a) \n",
    "                mn = min(mn, b) \n",
    "            if root.right:\n",
    "                a, b = dfs(root.right)\n",
    "                mx = max(mx, a) \n",
    "                mn = min(mn, b) \n",
    "            if mx == mn == root.val:\n",
    "                ans += 1 \n",
    "            return mx, mn \n",
    "        dfs(root) \n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Info:\n",
    "    def __init__(self,val = None, isSameTree = True):\n",
    "        self.val = val\n",
    "        self.isSameTree = isSameTree\n",
    "class Solution:\n",
    "    def countUnivalSubtrees(self, root: Optional[TreeNode]) -> int:\n",
    "        cnt = 0\n",
    "        def dfs(node):\n",
    "            nonlocal cnt\n",
    "            if node is None:\n",
    "                return Info()\n",
    "            L_I, R_I = dfs(node.left), dfs(node.right)\n",
    "            L_val = (L_I.val == None or L_I.val == node.val)\n",
    "            R_val = (R_I.val == None or R_I.val == node.val)\n",
    "            FLAG = L_I.isSameTree and R_I.isSameTree and L_val and R_val\n",
    "            cnt += FLAG\n",
    "            return Info(node.val,FLAG)\n",
    "        dfs(root)\n",
    "        return cnt\n",
    "        \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def countUnivalSubtrees(self, root: Optional[TreeNode]) -> int:\n",
    "        def checkUni(node, s):\n",
    "            if node:\n",
    "                s.add(node.val)\n",
    "                if len(s) == 2:\n",
    "                    return False\n",
    "                checkUni(node.left, s)\n",
    "                checkUni(node.right, s)\n",
    "            return len(s) == 1\n",
    "\n",
    "        self.res = 0\n",
    "        def dfs(node):\n",
    "            if node:\n",
    "                if checkUni(node, set()):\n",
    "                    self.res += 1\n",
    "                dfs(node.left)\n",
    "                dfs(node.right)\n",
    "        dfs(root)\n",
    "        return self.res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def countUnivalSubtrees(self, root: Optional[TreeNode]) -> int:\n",
    "        def dfs(node):\n",
    "            flag = True\n",
    "            cnt_left = 0\n",
    "            cnt_right = 0\n",
    "            if not node:\n",
    "                return True, 0\n",
    "            if not node.left and not node.right:\n",
    "                return True, 1\n",
    "            if node.left:\n",
    "                left, cnt_left = dfs(node.left)\n",
    "                if node.val == node.left.val and left:\n",
    "                    flag = True and flag\n",
    "                else:\n",
    "                    flag = False and flag\n",
    "            if node.right:\n",
    "                right, cnt_right = dfs(node.right)\n",
    "                if node.val == node.right.val and right:\n",
    "                    flag = True and flag\n",
    "                else:\n",
    "                    flag = False and flag\n",
    "            if flag:\n",
    "                cnt = cnt_left+cnt_right+1\n",
    "            else:\n",
    "                cnt = cnt_left+cnt_right\n",
    "            return flag, cnt\n",
    "\n",
    "        flag, cnt = dfs(root)\n",
    "        return cnt\n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def countUnivalSubtrees(self, root: Optional[TreeNode]) -> int:\n",
    "        cnt,error=0,0\n",
    "        def dfs(x):\n",
    "            nonlocal cnt,error\n",
    "            if x is None:\n",
    "                return None\n",
    "            cnt+=1\n",
    "            l=dfs(x.left)\n",
    "            r=dfs(x.right)\n",
    "            if (l is None or l==x.val) and (r is None or r==x.val):\n",
    "                return x.val\n",
    "            error+=1\n",
    "            return 1e9\n",
    "        dfs(root)\n",
    "        print(cnt,error)\n",
    "        return cnt-error"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def countUnivalSubtrees(self, root: Optional[TreeNode]) -> int:\n",
    "        if not root:\n",
    "            return 0\n",
    "        ans=0\n",
    "        def dfs(r):\n",
    "            nonlocal ans \n",
    "           # if not r:\n",
    "               # return True \n",
    "\n",
    "            if r.left and r.right:\n",
    "                a=dfs(r.left)\n",
    "                b=dfs(r.right)\n",
    "                if a==True and b==True and r.left.val==r.right.val==r.val :\n",
    "                    ans+=1\n",
    "                    return True\n",
    "            elif r.left:\n",
    "                a=dfs(r.left)\n",
    "                if a==True  and r.left.val==r.val :\n",
    "                    ans+=1\n",
    "                    return True\n",
    "            elif r.right:\n",
    "                b=dfs(r.right)\n",
    "                if b==True  and r.right.val==r.val :\n",
    "                   # print(r)\n",
    "                    ans+=1\n",
    "                    return True\n",
    "            elif not r.left and not r.right:\n",
    "                ans+=1\n",
    "               # print(r)\n",
    "                return True\n",
    "            else:\n",
    "                return False\n",
    "\n",
    "        dfs(root)\n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def countUnivalSubtrees(self, root: Optional[TreeNode]) -> int:\n",
    "        self.res = 0 \n",
    "\n",
    "        self.traverse(root)\n",
    "\n",
    "        return self.res \n",
    "\n",
    "    def traverse(self, root):\n",
    "        if root is None:\n",
    "            return set([])\n",
    "\n",
    "        left_tree = self.traverse(root.left)\n",
    "        right_tree = self.traverse(root.right)\n",
    "\n",
    "        values = set([root.val])\n",
    "        values |= left_tree\n",
    "        values |= right_tree \n",
    "\n",
    "        if len(values) == 1:\n",
    "            self.res += 1\n",
    "\n",
    "        return values"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def countUnivalSubtrees(self, root: Optional[TreeNode]) -> int:\n",
    "        self.res = 0 \n",
    "\n",
    "        self.traverse(root)\n",
    "\n",
    "        return self.res \n",
    "\n",
    "    def traverse(self, root):\n",
    "        if root is None:\n",
    "            return set([])\n",
    "\n",
    "        left_tree = self.traverse(root.left)\n",
    "        right_tree = self.traverse(root.right)\n",
    "\n",
    "        values = set([root.val])\n",
    "        values |= left_tree\n",
    "        values |= right_tree \n",
    "\n",
    "        if len(values) == 1:\n",
    "            self.res += 1\n",
    "\n",
    "        return values"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def countUnivalSubtrees(self, root: Optional[TreeNode]) -> int:\n",
    "        res = 0\n",
    "        def dfs(node):\n",
    "            nonlocal res\n",
    "            if not node:\n",
    "                return False\n",
    "            if not node.left and not node.right:\n",
    "                res += 1\n",
    "                return True\n",
    "            \n",
    "            left = dfs(node.left)\n",
    "            right = dfs(node.right)\n",
    "            if left and right and node.val == node.left.val == node.right.val:\n",
    "                res += 1\n",
    "                return True\n",
    "\n",
    "            if node.left and left and not node.right and node.val == node.left.val:\n",
    "                res += 1\n",
    "                return True\n",
    "            \n",
    "            if node.right and right and not node.left and node.val == node.right.val:\n",
    "                res += 1\n",
    "                return True\n",
    "            \n",
    "            return False\n",
    "        dfs(root)\n",
    "        return res\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def countUnivalSubtrees(self, root: Optional[TreeNode]) -> int:\n",
    "        # if not root: return 0\n",
    "        self.ans  = 0\n",
    "        def dfs(node):\n",
    "            if not node:\n",
    "                return None\n",
    "            if not node.left and not node.right:\n",
    "                self.ans +=1\n",
    "                return node.val\n",
    "            left = dfs(node.left)\n",
    "            right = dfs(node.right)\n",
    "            if left == right == node.val or (left is None and right == node.val) or (right is None and left == node.val):\n",
    "                self.ans +=1\n",
    "                return node.val\n",
    "            return inf\n",
    "\n",
    "        dfs(root)\n",
    "        return self.ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def countUnivalSubtrees(self, root: Optional[TreeNode]) -> int:\n",
    "        res = 0\n",
    "        def helper(root: Optional[TreeNode])->bool:\n",
    "            nonlocal res\n",
    "            if not root:\n",
    "                return True\n",
    "            leftRoot = helper(root.left)\n",
    "            rightRoot = helper(root.right)\n",
    "            if leftRoot == False or rightRoot == False:\n",
    "                return False\n",
    "\n",
    "            if root.left == None and root.right == None:\n",
    "                res += 1\n",
    "                return True\n",
    "            if root.left != None and root.right != None:\n",
    "                if leftRoot and rightRoot:\n",
    "                    if root.val == root.right.val and root.val == root.left.val:\n",
    "                        res += 1\n",
    "                        return True\n",
    "                    else:\n",
    "                        return False\n",
    "            if root.left:\n",
    "                if leftRoot and root.val == root.left.val:\n",
    "                    res += 1\n",
    "                    return True\n",
    "            if root.right:\n",
    "                if rightRoot and root.val == root.right.val:\n",
    "                    res += 1\n",
    "                    return True\n",
    "            return False\n",
    "        helper(root)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def countUnivalSubtrees(self, root: Optional[TreeNode]) -> int:\n",
    "        self.ans = 0\n",
    "        def dfs(node):\n",
    "            if not node:\n",
    "                return None\n",
    "            if not node.left and not node.right:\n",
    "                self.ans +=1\n",
    "                return node.val\n",
    "            left = dfs(node.left)\n",
    "            right = dfs(node.right)\n",
    "\n",
    "            if left == right == node.val or (left is None and right == node.val) or  (right is None and left == node.val):\n",
    "                self.ans +=1\n",
    "                return node.val\n",
    "            return inf\n",
    "        \n",
    "        dfs(root)\n",
    "        return self.ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def countUnivalSubtrees(self, root):\n",
    "        self.count = 0\n",
    "        self.is_valid_part(root, 0)\n",
    "        return self.count\n",
    "\n",
    "\n",
    "    def is_valid_part(self, node, val):\n",
    "\n",
    "        # considered a valid subtree\n",
    "        if node is None: return True\n",
    "\n",
    "        # check if node.left and node.right are univalue subtrees of value node.val\n",
    "        if not all([self.is_valid_part(node.left, node.val),\n",
    "                    self.is_valid_part(node.right, node.val)]):\n",
    "            return False\n",
    "\n",
    "        # if it passed the last step then this a valid subtree - increment\n",
    "        self.count += 1\n",
    "\n",
    "        # at this point we know that this node is a univalue subtree of value node.val\n",
    "        # pass a boolean indicating if this is a valid subtree for the parent node\n",
    "        return node.val == val"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def countUnivalSubtrees(self, root: Optional[TreeNode]) -> int:\n",
    "        cnt = 0\n",
    "        def dfs(root):\n",
    "            nonlocal cnt\n",
    "            if not root:\n",
    "                return \"Y\"\n",
    "\n",
    "            left, right = dfs(root.left), dfs(root.right)\n",
    "            if left in (\"Y\", root.val) and right in (\"Y\", root.val):\n",
    "                cnt += 1\n",
    "                return root.val\n",
    "            else:\n",
    "                return \"N\"\n",
    "        \n",
    "        dfs(root)\n",
    "        return cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def countUnivalSubtrees(self, root: Optional[TreeNode]) -> int:\n",
    "        cnt = 0\n",
    "        def dfs(root):\n",
    "            nonlocal cnt\n",
    "            if not root:\n",
    "                return \"Y\"\n",
    "\n",
    "            left, right = dfs(root.left), dfs(root.right)\n",
    "            if left in (\"Y\", root.val) and right in (\"Y\", root.val):\n",
    "                cnt += 1\n",
    "                return root.val\n",
    "            else:\n",
    "                return \"N\"\n",
    "        \n",
    "        dfs(root)\n",
    "        return cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def countUnivalSubtrees(self, root: Optional[TreeNode]) -> int:\n",
    "        def count_node(node):\n",
    "            if not node:\n",
    "                return 0, None\n",
    "\n",
    "            count_left, val_left = count_node(node.left)\n",
    "            count_right, val_right = count_node(node.right)\n",
    "\n",
    "            count = count_left + count_right\n",
    "            if val_left in (None, node.val) and val_right in (None, node.val):\n",
    "                return count + 1, node.val\n",
    "            return count, sys.maxsize\n",
    "\n",
    "        ret, _ = count_node(root)\n",
    "        return ret\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def countUnivalSubtrees(self, root: TreeNode) -> int:\n",
    "        self.ans = 0\n",
    "        def dfs(node):\n",
    "            if not node:\n",
    "                return None\n",
    "            if not node.left and not node.right:\n",
    "                self.ans += 1\n",
    "                return node.val\n",
    "            left = dfs(node.left)\n",
    "            right = dfs(node.right)\n",
    "            if left == right == node.val or (left is None and right == node.val) or (right is None and left == node.val):\n",
    "                self.ans += 1\n",
    "                return node.val\n",
    "            return inf #### 生成终结值\n",
    "        \n",
    "        dfs(root)\n",
    "        return self.ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def countUnivalSubtrees(self, root: Optional[TreeNode]) -> int:\n",
    "        if not root: return 0\n",
    "        ans = 0\n",
    "        def dfs(root):\n",
    "            nonlocal ans\n",
    "            if not root: return False\n",
    "            if not root.left and not root.right:\n",
    "                ans += 1\n",
    "                return True\n",
    "            \n",
    "            unique = True\n",
    "            if root.left:\n",
    "                unique = dfs(root.left) and unique and root.left.val == root.val\n",
    "            if root.right:\n",
    "                unique = dfs(root.right) and unique and root.right.val == root.val\n",
    "            ans += unique\n",
    "            return unique\n",
    "        dfs(root)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def countUnivalSubtrees(self, root: TreeNode) -> int:\n",
    "        self.ans = 0\n",
    "        def dfs(node):\n",
    "            if not node:\n",
    "                return None\n",
    "            if not node.left and not node.right:\n",
    "                self.ans += 1\n",
    "                return node.val\n",
    "            left = dfs(node.left)\n",
    "            right = dfs(node.right)\n",
    "            if left == right == node.val or (left is None and right == node.val) or (right is None and left == node.val):\n",
    "                self.ans += 1\n",
    "                return node.val\n",
    "            return inf\n",
    "        \n",
    "        dfs(root)\n",
    "        return self.ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def countUnivalSubtrees(self, root: Optional[TreeNode]) -> int:\n",
    "        def dfs(root):\n",
    "            if root:\n",
    "                path.append(root)\n",
    "                dfs(root.left)\n",
    "                dfs(root.right)\n",
    "        path = []\n",
    "        dfs(root)\n",
    "\n",
    "        def check(root):\n",
    "            if not root:\n",
    "                return []\n",
    "            return [root.val] + check(root.left) + check(root.right)\n",
    "        ans = 0\n",
    "        for i in path:\n",
    "            if len(set(check(i))) == 1:\n",
    "                ans += 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Info:\n",
    "    def __init__(self,val = None, isSameTree = True):\n",
    "        self.val = val\n",
    "        self.isSameTree = isSameTree\n",
    "class Solution:\n",
    "    def countUnivalSubtrees(self, root: Optional[TreeNode]) -> int:\n",
    "        cnt = 0\n",
    "        def dfs(node):\n",
    "            nonlocal cnt\n",
    "            if node is None:\n",
    "                return Info()\n",
    "            l_I, r_I = dfs(node.left), dfs(node.right)\n",
    "            if l_I.isSameTree and r_I.isSameTree:\n",
    "                if (l_I.val == None or l_I.val == node.val) and (r_I.val == None or r_I.val == node.val):\n",
    "                    cnt += 1\n",
    "                    return Info(node.val, True)\n",
    "            return Info(node.val,False)\n",
    "        dfs(root)\n",
    "        return cnt\n",
    "        \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def countUnivalSubtrees(self, root: Optional[TreeNode]) -> int:\n",
    "        self.ans = 0\n",
    "\n",
    "        if not root:\n",
    "            return 0\n",
    "\n",
    "        def checkUnivalSubtree(root):\n",
    "            if not root:\n",
    "                return False\n",
    "            if not root.left and not root.right:\n",
    "                return True\n",
    "            if (not root.left or (checkUnivalSubtree(root.left) and root.left.val == root.val)) and (not root.right or (checkUnivalSubtree(root.right) and root.right.val == root.val)):\n",
    "                return True\n",
    "            return False\n",
    "        \n",
    "        def dfs(root):\n",
    "            if checkUnivalSubtree(root):\n",
    "                self.ans += 1\n",
    "            if root.left:\n",
    "                dfs(root.left)\n",
    "            if root.right:\n",
    "                dfs(root.right)\n",
    "        \n",
    "        dfs(root)\n",
    "\n",
    "        return self.ans\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def countUnivalSubtrees(self, root: Optional[TreeNode]) -> int:\n",
    "        anw = 0\n",
    "\n",
    "        def dfs(node):\n",
    "            nonlocal anw\n",
    "            if not node:\n",
    "                return True\n",
    "            \n",
    "            left = dfs(node.left)\n",
    "            right = dfs(node.right)\n",
    "\n",
    "            if not left or not right:\n",
    "                return False\n",
    "            \n",
    "            if node.left and node.val != node.left.val:\n",
    "                return False\n",
    "            \n",
    "            if node.right and node.val != node.right.val:\n",
    "                return False\n",
    "            anw += 1\n",
    "\n",
    "            return True\n",
    "        \n",
    "        dfs(root)\n",
    "        return anw\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def countUnivalSubtrees(self, root: Optional[TreeNode]) -> int:\n",
    "        if not root: return 0\n",
    "        res = 0\n",
    "        \n",
    "        def check(node: TreeNode) -> bool:\n",
    "            nonlocal res\n",
    "            if not node.left and not node.right:\n",
    "                res += 1\n",
    "                return True\n",
    "            ans = True\n",
    "            if node.left:\n",
    "                ans = check(node.left) and ans and node.left.val == node.val\n",
    "            if node.right:\n",
    "                ans = check(node.right) and ans and node.right.val == node.val\n",
    "            res += ans\n",
    "            return ans\n",
    "\n",
    "        check(root)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def countUnivalSubtrees(self, root: Optional[TreeNode]) -> int:\n",
    "        res=0\n",
    "        if(root==None):\n",
    "            return 0\n",
    "        def _foo(root:TreeNode):\n",
    "            nonlocal res\n",
    "            if(root.left==None and root.right==None):\n",
    "                res+=1\n",
    "                return root.val\n",
    "            \n",
    "            l_v,r_v=-1001,-1001\n",
    "            if(root.left):\n",
    "                l_v=_foo(root.left)\n",
    "                \n",
    "            if(root.right):  \n",
    "                r_v=_foo(root.right)\n",
    "\n",
    "            if((l_v==-1001 or root.val==l_v) and (r_v==-1001 or root.val==r_v)):\n",
    "                res+=1\n",
    "                return root.val\n",
    "            else:\n",
    "                return None\n",
    "        \n",
    "        _foo(root)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def countUnivalSubtrees(self, root: Optional[TreeNode]) -> int:\n",
    "        ans = 0\n",
    "        def dfs(node: Optional[TreeNode]) -> bool:\n",
    "            if not node:\n",
    "                return True\n",
    "            l = dfs(node.left)\n",
    "            r = dfs(node.right)\n",
    "            nonlocal ans\n",
    "            # 子节点符合条件 and 当前节点和子节点也符合条件\n",
    "            if l and r and (not node.left or node.left.val == node.val) and (not node.right or node.right.val == node.val):\n",
    "                ans += 1\n",
    "                return True\n",
    "            return False\n",
    "        dfs(root)\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def countUnivalSubtrees(self, root: Optional[TreeNode]) -> int:\n",
    "        \n",
    "        def is_tree_unival(root: Optional[TreeNode]) -> tuple((bool, int)):\n",
    "            if not root:\n",
    "                return (False, 0)\n",
    "            if not root.left and not root.right:\n",
    "                return (True, 1)\n",
    "            if root.left and root.right:\n",
    "                # print(\"root.val\", root.val)\n",
    "                # print(\"root.left\", root.left)\n",
    "                # print(\"root.right\", root.right)\n",
    "                left_res = is_tree_unival(root.left)\n",
    "                right_res = is_tree_unival(root.right)\n",
    "                # print(\"left_res\", left_res)\n",
    "                # print(\"right_res\", right_res)\n",
    "                if left_res[0] and right_res[0] and root.val == root.left.val == root.right.val:\n",
    "                    return (True, left_res[1] + right_res[1] + 1)\n",
    "                else:\n",
    "                    return (False, left_res[1] + right_res[1])\n",
    "            if root.left:\n",
    "                left_res = is_tree_unival(root.left)\n",
    "                if left_res[0] and root.val == root.left.val:\n",
    "                    return (True, left_res[1] + 1)\n",
    "                else:\n",
    "                    return (False, left_res[1])\n",
    "            if root.right:\n",
    "                # print(\"root.val\", root.val)\n",
    "                # print(\"root.right\", root.right)\n",
    "                right_res = is_tree_unival(root.right)\n",
    "                # print(\"right_res\", right_res)\n",
    "                if right_res[0] and root.val == root.right.val:\n",
    "                    return (True, right_res[1] + 1)\n",
    "                else:\n",
    "                    return (False, right_res[1])            \n",
    "        \n",
    "        return is_tree_unival(root)[1]"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
